home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
answrbok
/
6_11.lha
/
6_11
/
6_11_add.c
next >
Wrap
Text File
|
1993-08-08
|
4KB
|
176 lines
* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
* The C++ Answer Book */
* Tony Hansen */
* All rights reserved. */
*
Add u[1..n] + v[1..n] to form w[0..n]
Based on:
The Art of Computer Programming, volume 2
D. Knuth, Section 4.3.1, Algorithm A
/
include <arbint.h>
include <debug.h> /* DELETE */
rbint operator+(const arbint& u, const arbint& v)
int ulen = u.p->length;
int vlen = v.p->length;
int wlen = max(ulen, vlen) + 1;
ARB_type *wv = new ARB_type[wlen];
ARB_type *uv = u.p->value;
ARB_type *vv = v.p->value;
f (debug&64)/*DELETE*/ cerr << "operator+\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "u=", uv, ulen);
f (debug&64)/*DELETE*/ outputarb(cerr, "v=", vv, vlen);
f (debug&64)/*DELETE*/ outputarb(cerr, "w(beg)=", wv, wlen);
/*
A1 [Initialize]
set j <- n
k <- 0
{ modification: uj for u, vj for v }
A3(a) [Loop on j]
decrease j by one
{ modification: decrease uj and vj }
*/
f (debug&64)/*DELETE*/ cerr << "before first loop, uj=" << (ulen-1) << ", vj=" << (vlen-1) << ", wj=" << (wlen-1) << "\n";
ARB_Ltype k = 0;
for (int uj = ulen - 1, vj = vlen - 1, wj = wlen - 1;
uj >= 0 && vj >= 0;
uj--, vj--, wj-- )
{
/*
A2(a) [Add digits]
set w[j] <- (u[j] + v[j] + k) mod b
{ modification: w[wj] <-
(u[uj] + v[vj] + k) mod b }
*/
ARB_Ltype t = uv[uj] + vv[vj] + k;
wv[wj] = t; // % ARB_base;
/*
A2(b)
k <- (u[j] + v[j] + k) / b
*/
k = (t / ARB_base) ? 1 : 0;
}
f (debug&64)/*DELETE*/ cerr << "after first loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "w(now)=", wv, wlen);
/*
NOTE: either (uj >= 0) or (vj >= 0),
but not both. As long as the carry is
non-zero, it must be added to the next
digit.
*/
if (uj >= 0)
{
/*
Take care of u[1..uj].
*/
for ( ; k != 0 && uj >= 0; uj--, wj-- )
{
ARB_Ltype t = uv[uj];
t += k;
wv[wj] = t; // % ARB_base;
k = (t / ARB_base) ? 1 : 0;
}
f (debug&64)/*DELETE*/ cerr << "after second loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "w(now)=", wv, wlen);
/*
The carry is now zero, so any
remaining digits can be copied.
*/
while (uj >= 0)
wv[wj--] = uv[uj--];
f (debug&64)/*DELETE*/ cerr << "after first copy, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "w(now)=", wv, wlen);
/*
If there are any digits left to be filled in
(there should be at most 1)
they must be filled with either 0
or ~0 depending on the sign of wv[wj+1]
*/
if (wj >= 0)
{
const ARB_type hibit = (ARB_base >> 1);
const ARB_type rest = (wv[wj+1] & hibit) ? ~0 : 0;
do {
wv[wj--] = rest;
} while (wj >= 0);
}
}
else if (vj >= 0)
{
/*
Take care of v[1..vj]
*/
for ( ; k != 0 && vj >= 0; vj--, wj-- )
{
ARB_Ltype t = vv[vj];
t += k;
wv[wj] = t; // % ARB_base;
k = (t / ARB_base) ? 1 : 0;
}
f (debug&64)/*DELETE*/ cerr << "after third loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "w(now)=", wv, wlen);
/*
The carry is now zero, so any
remaining digits can be copied.
*/
while (vj >= 0)
wv[wj--] = vv[vj--];
f (debug&64)/*DELETE*/ cerr << "after second copy, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
f (debug&64)/*DELETE*/ outputarb(cerr, "w(now)=", wv, wlen);
/*
If there are any digits left
(there should be at most 1)
they must be filled with either 0
or ~0 depending on the sign of wv[wj+1]
*/
if (wj >= 0)
{
const ARB_type hibit = (ARB_base >> 1);
const ARB_type rest = (wv[wj+1] & hibit) ? ~0 : 0;
do {
wv[wj--] = rest;
} while (wj >= 0);
}
}
else
{
/*
If there is a digit left (there should be at
most 1), it should be set to k.
Because we are dealing with 2's complement,
a carry here means that the number must be
sign-extended; otherwise the digit is set to 0.
A3(b)
Set w[0] <- k
{ modification,
w[0] <- k ? sign(w[wj]) ? 0
}
*/
const ARB_type hibit = (ARB_base >> 1);
const ARB_type rest = (k && (wv[wj+1] & hibit)) ? ~0 : 0;
while (wj >= 0)
wv[wj--] = rest;
}
/* Normalize and return */
f (debug&64)/*DELETE*/ outputarb(cerr, "w(end)=", wv, wlen);
arbint w(wv, wlen);
return w;